package leetcode_500;

import java.util.Stack;

public class FlattenAMultilevelDoublyLinkedList_430 {
	class Node {
	    public int val;
	    public Node prev;
	    public Node next;
	    public Node child;

	    public Node() {}

	    public Node(int _val,Node _prev,Node _next,Node _child) {
	        val = _val;
	        prev = _prev;
	        next = _next;
	        child = _child;
	    }
	}
	
	public static void main(String[] args) {
		FlattenAMultilevelDoublyLinkedList_430 test=new FlattenAMultilevelDoublyLinkedList_430();
		
	}
	
	public Node flatten(Node head) {
		if(head==null)
			return head;
        Stack<Node> stack=new Stack<Node>();
        Node run=head.next,pre=head;
        while(run!=null||!stack.isEmpty()) {
        	if(run==null) {//把栈里的拿出来
        		Node now=stack.pop();
        		pre.next=now;
        		now.prev=pre;
        		run=now;
        	}
        	else {//继续遍历
		        while(run!=null) {
		        	if(run.child!=null) {
		        		stack.push(run.next);
		        		run.next=run.child;
		        		run.prev=run;
		        		run.child=null;
		        		pre=run;
		        		run=run.next;
		        	}
		        	else {
		        		pre=run;
		        		run=run.next;
		        	}
		        }
        	}
        }
		return head;
    	}
	public void print(Node head) {
		Node run=head;
		while(run!=null) {
			System.out.print(run.val+" ");
			run=run.next;
		}
	}
	
}
